package 热题100;

import java.util.ArrayList;
import java.util.List;

public class 热题22括号生成 {


    public static void main(String[] args) {
        热题22括号生成 o = new 热题22括号生成();
        List<String> list = o.generateParenthesis(2);
        System.out.println(list);
    }

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(list,n,sb,0,0);
        return list;
    }

    private void dfs(List<String> list, int n, StringBuilder sb, int lCount, int rCount) {

        //如果开括号个数大于n或者右括号的个数大于左括号，回溯
        if (lCount > n || rCount > lCount){
            return;
        }

        //如果开括号 + 闭括号 == 2 * n，说明括号生产匹配完成，添加到list集合中
        if (sb.length() == 2 * n){
            list.add(sb.toString());
            return;
        }

        //每次遍历后都需要把sb中添加的符号删除
        dfs(list,n,sb.append("("),lCount+1,rCount);
        sb.delete(sb.length()-1,sb.length());
        dfs(list,n,sb.append(")"),lCount,rCount+1);
        sb.delete(sb.length()-1,sb.length());
    }
}
